constructive algorithms greedy math *1500

Please click on ads to support us..

Python Code:

from math import floor,ceil

n=int(input())
arr=[]
for i in range(n):
    arr.append(float(input()))
res=[floor(i) for i in arr]
s=sum(res)
i=0
while s and i<n:
    if ceil(arr[i])!=res[i]:
        res[i]=ceil(arr[i])
        s+=1
    i+=1

print(*res,sep="\n")

C++ Code:

#include "bits/stdc++.h"
//#include <functional>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define PI 2 * acos(0)
#define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << " = " << x << '\n';
#else
#define debug(x)
#endif
#define LOOP printf("LOOP!!")
#define YES cout << "YES" << '\n'
#define NO cout << "NO" << '\n'
#define TIME cerr << "\nTime:" << 1000 * clock() / CLOCKS_PER_SEC << '\n';
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define ll long long
#define MOD 1000000007
#define ull unsigned long long
#define endl "\n"
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define PQ priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;

void show(vector<ll> &v)
{
    for (auto &it : v)
        cout << it << " ";

    cout << '\n';
}

//............................//


int main()
{

     FAST;
     int n;
     cin>>n;
     vector<double>v(n);
     for(auto &it:v)cin>>it;
     vector<ll>res;
     set<int>korajabena;
     ll s=0;
     for(int i=0;i<n;i++){
        if(ceil(v[i])==(v[i])){
            korajabena.insert(i);
        }
        res.push_back(floor(v[i]));
        s+=floor(v[i]);
        //cout<<s<<endl;
     }
     ///// shob floor nisi jah baal, eibar dekhbo koto kom ase ek ek kore barai dbo its possible because
     /// number of floor is <= n and the sum is guaranteed to be 0 ,it is said.

     if(s==0){
        show(res);
     }
     else{
       // cout<<s<<endl;
        //cout<<s<<endl;
        for(int i=0;i<n;i++){
            if(korajabena.find(i)!=korajabena.end())continue;
            s++;
            res[i]++;
            if(s==0)break;
        }
        show(res);
     }    
    
     return 0;
}

/// sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
///  is_sorted(all(v))
// always formulate your equation in multiplication form not div
/// fflush(stdin)
// are you using same variable inside another if or else ?
  	  		 		 				  		  		


Comments

Submit
0 Comments
More Questions

465A - inc ARG
1260A - Heating
1740D - Knowledge Cards
1028A - Find Square
1370B - GCD Compression
888D - Almost Identity Permutations
1106C - Lunar New Year and Number Division
849B - Tell Your World
1650E - Rescheduling the Exam
899C - Dividing the numbers
1023C - Bracket Subsequence
1579D - Productive Meeting
1749E - Cactus Wall
1682C - LIS or Reverse LIS
578A - A Problem about Polyline
1038E - Maximum Matching
1141C - Polycarp Restores Permutation
1685A - Circular Local MiniMax
432B - Football Kit
10C - Digital Root
743B - Chloe and the sequence
909D - Colorful Points
1283C - Friends and Gifts
605B - Lazy Student
1687B - Railway System
61D - Eternal Victory
588B - Duff in Love
12C - Fruits
447B - DZY Loves Strings
325A - Square and Rectangles